<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
<head>
  <title>Konecne automaty</title>
  <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  <meta name="Author" content="Bronislav Houdek">
  <link rel="stylesheet" type="text/css" href="/fja/css/help.css">
</head>
<style type="text/css">
</style>
<body>
  
<a name="fa"><h1>DFA, NFA a EFA - (ne)deterministicky konecny automat (s epsilon kroky)</h1></a>
<p>
  DFA - deterministicky konecny automat.<br>
  NFA - nedeterministicky konecny automat.<br>
  EFA - nedeterministicky konecny automat s epsilon kroky<br>
  Definice se sklada ze 3 casti: inicialni stav, prechodova funkce, konecne stavy.<br>
  Pri ekvivalenci automatu musi mit automaty stejnou vst.abecedu a musi byt jazykove ekvivalentni, tzn. na poradi pravidel, pojmenovani, totalnosti, minimalnosti atp. nezalezi. Pokud je pozadavek tak na totalnost/ minimalnost atp., tak musi byt zvolen typ TOT,MIN atp.<br>
  V pripade EFA lze pouzit take epsilon.<br>
  V pripade pouziti epsilon v NFA bude automat vyhodnocen take, ale bude indikovana chyba, ze bylo pouzito epsilon.<br>
</p>
<ul>
  <li><a href="examples.html#dfa">Priklad DFA</a>
  <li><a href="examples.html#nfa">Priklad NFA</a>
  <li><a href="examples.html#efa">Priklad EFA</a>
  <li><a href="#init_fa">Inicialni stav</a>
  <li><a href="#prechod_dfa">Prechodova funkce pro DFA</a>
  <li><a href="#prechod_nfa">Prechodova funkce pro NFA</a>
  <li><a href="#final">Konecne stavy</a>
  <li><a href="#stav">Stavy FA a znaky vst.abecedy FA</a>
</ul>

<a name="init_fa"><h2>Inicialni stav</h2></a>
<p>
  Je definovan pravidlem: "<span>init=X</span>" - kde "<span>X</span>" je nazev inicialniho <a href="#stav">stavu</a>.
  Pokud neni pravidlo uvedeno, je urcen za inicialni stav prvni nalezeny stav.
</p>

<a name="prechod_dfa"><h2>Prechodova funkce DFA</h2></a>
<p>
  Prechodova funkce je definovana pravidly: "<span>(X,y)=Z</span>" - coz znamena prechod ze stavu "<span>X</span>" pod znakem "<span>y</span>" do stavu "<span>Z</span>".
</p>

<a name="prechod_nfa"><h2>Prechodova funkce NFA a EFA(NFA s epsilon kroky)</h2></a>
<p>
  Prechodova funkce je definovana pravidly: "<span>(X,y)={Z1,Z2,...}</span>" - coz znamena prechod ze stavu "<span>X</span>" pod znakem "<span>y</span>" do stavu "<span>Z1</span>" nebo "<span>Z2</span>" ... .<br>
</p>

<a name="final"><h2>Finalni stavy</h2></a>
<p>
  Finalni <a href="#stav">stavy</a> jsou definovany pravidlem: "<span>F={X,Y,...}</span>" - kde "<span>X</span>","<span>Y</span>" jsou nazvy konecnych stavu. Pokud neni uveden, neni definovan zadny konecny stav, popr lze uvest tez jen - "<span>F={}</span>".
</p>

<a name="stav"><h2>Stavy FA a znaky vst.abecedy FA</h2></a>
<p>
  Nazev stavu, popr. znaku vst.abecedy je jakykoliv retezec znaku, s vyjimkou specialnich znaku a znaku neviditelnych.<br>
  Specialni znaky: "<span>{</span>", "<span>}</span>", "<span>(</span>", "<span>)</span>", "<span>=</span>", "<span>\</span>", "<span>,</span>" a mezera "<span> </span>".
  Specialni znak je mozno uvest znakem "<span>\</span>".
  Bile znaky krom mezery nelze v nazvu stavu ci vst.abecedy uvest.<br>
  Epsilon - prazdny znak - je definovan specialni sekvenci: "<span>\e</span>". Pokud je epsilon pouzito v nazvu stavu nebo znaku vst.abecedy a jsou pouzity i jine znaky tak je ignorovano tzn. "<span>(B\eA,\e\e)=Z</span>"="<span>(BA,\e)=Z</span>". Pouze epsilon jako nazev stavu, je indikovano jako chyba.
</p>

<a name="tot"><h1>TOT - totalni automat</h1></a>
<p>
  Stejna pravidla jak pro DFA. Automat musi byt ovsem take totalni a musi mit stejnou abecedu jako predloha.<br>
  Tzn. ve vsech stavech musi byt definovana pravidla pro kazdy znak vst.abecedy co byl uveden a pro zadny jiny nesmi byti pravidla uvedena.
</p>

<a name="min"><h1>MIN - minimalni konecny automat</h1></a>
<p>
    Stejna pravidla jak pro DFA. Automat musi byt navic minimalni a totalni.
</p>

<a name="can"><h1>CAN - kanonicky konecny automat</h1></a>
<p>
  Stejna pravidla jak pro DFA. Automat musi byt kanonicky.<br>
  Kanonicky automat <b>nemusi</b> byt totalni, <b>nemusi</b> mit shodnou abecedu jako predloha a nesmi obsahovat nedosazitelne stavy.<br>
  Stavy musi byt pojmenovany neprerusenou posloupnosti - znaku "<span>A</span>".."<span>Z</span>",
  pokud ma 26 a mene stavu, pokud ma vice nez 26 stavu, tak musi by stavy pojmenovany neprerusenou posloupnosti cisel "<span>0</span>"..n, kde n je pocet stavu.
</p>

<a name="toc"><h1>TOC - totalni kanonicky konecny automat</h1></a>
<p>
  Prunik automatu TOT a CAN.<br>
  Tzn. automat musi byt totalni a kanonicky.
</p>

<a name="mic"><h1>MIC - minimalni kanonicky konecny automat</h1></a>
<p>
  Prunik automatu MIN a CAN.<br>
  Tzn. automat musi byt minimalni a kanonicky.
</p>

</body>
</html>
